package com.bt.springboot.demo.algorithm.leetcode;

/**
 * 5.最长回文子串
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 *
 * @author zkx
 * @Date 2021/7/23 10:37
 */
public class Topic05 {
	public static void main(String[] args) {
		Topic05 topic05 = new Topic05();
		String s = "babadaabbaad";
		System.out.println(topic05.longestPalindrome(s));
	}

	public String longestPalindrome(String s) {
		int len = s.length();
		if (len < 2) {
			return s;
		}

		int maxLen = 2;
		String res = s.substring(0, 1);

		// 枚举所有长度大于等于2的子串
		for (int i = 0; i < len - 1; i++) {
			for (int j = i + 1; j < len; j++) {
				if (j - i + 1 >= maxLen && valid(s, i, j)) {
					maxLen = j - i + 1;
					res = s.substring(i, j + 1);
				}
			}
		}

		return res;
	}

	public boolean valid(String s, int left, int right) {
		// 验证子串s[left,right] 是否为回文串
		while (left < right) {
			if (s.charAt(left) != s.charAt(right)) {
				return false;
			}
			left++;
			right--;
		}
		return true;
	}
}
